package com.shawn.datastructure.stack;

import java.util.Stack;

public class LongestValidParentheses {

	public int longestValidParentheses(String s) {
		if (s == null || s.isEmpty()) {
			return 0;
		}
		int length = 0;
		Stack<Integer> stack = new Stack<>();
		char[] chars = s.toCharArray();
//		stack.push(-1);
		int left = -1;
		for (int i = 0; i < chars.length; i++) {
			if ('(' == chars[i]) {
				stack.push(i);
			} else {
				if (stack.isEmpty()) {
					left = i;
				} else {
					stack.pop();
					if (stack.isEmpty()) {
						length = Math.max(length, i - left);
					} else {
						length = Math.max(length, i - stack.peek());
					}
				}
//				stack.pop();
//				if (stack.isEmpty()) {
//					stack.push(i);
//				} else {
//					length = Math.max(length, i - stack.peek());
//				}
			}
		}
		return length;
	}
}
